#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef struct ListNode
{
    int val;
    struct ListNode *next;
}ListNode;
typedef struct 
{
    // front队首,rear队尾
    ListNode *front, *rear;
    int size;
}LinkedListQueue;

/*构造函数*/
LinkedListQueue *newLinkedListQueue()
{
    LinkedListQueue *q = (LinkedListQueue *)malloc(sizeof(LinkedListQueue));
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
    return q;
}
/*析构函数*/
void delLinkedListQueue(LinkedListQueue *q)
{
    for (int i = 0; i < q->size; i++)
    {
        ListNode *num = q->front;
        q->front = q->front->next;
        free(num);
    }
    free(q);
}
/*获取长度*/
int size(LinkedListQueue *q)
{
    return q->size;
}
/*是否为空*/
bool isEmpty(LinkedListQueue *q)
{
    return q->size == 0;
}
/*入队*/
void push(LinkedListQueue *q, int num)
{
    ListNode *tmp = (ListNode *)malloc(sizeof(ListNode));
    tmp->val = num;
    tmp->next = NULL;
    q->size++;    
    if (!q->front)
    {
        q->front = tmp;   
        q->rear = tmp;
    }else
    {
        q->rear->next = tmp;
        q->rear = tmp;
    }
}
/*访问队首*/
int peek(LinkedListQueue *q)
{
    assert(q->size && q->front);
    return q->front->val;
}
/*出队*/
int pop(LinkedListQueue *q)
{
    int val = peek(q);
    ListNode *num = q->front;
    q->front = q->front->next;
    free(num);
    q->size--;
    return val;
}
/*打印队列*/
void printQueue(LinkedListQueue *q)
{
    if (q->size == 0)
    {
        printf("队列为空\n");
        return;
    }
    ListNode *nums = q->front;
    while (nums != q->rear)
    {
        printf("%d ", nums->val);
        nums = nums->next;
    }
    printf("%d\n", nums->val);
}

int main(int argc, char const *argv[])
{
    // 初始化，头1-3-2-5-4
    LinkedListQueue *q = newLinkedListQueue();
    push(q, 1);
    push(q, 3);
    push(q, 2);
    push(q, 5);
    push(q, 4);
    printQueue(q);
    printf("队首:%d\n", peek(q));

    // 出队
    pop(q);
    printQueue(q);
    // 队首
    printf("队首:%d\n", peek(q));

    // 析构
    delLinkedListQueue(q);
    return 0;
}
